package lc8;

import java.util.ArrayList;
import java.util.List;

public class Solution {

        public int maxLength(List<String> arr) {
            String weget = arr.get(0);
            int max = 0;

            List<String> anses = new ArrayList<String>();
            for (int i = 0; i < arr.size(); i++){
                if (ifSame(arr.get(i)))
                    search(arr, arr.get(i), i+1, anses);
            }

            for (int i = 0; i < anses.size(); i++){
                if (max < anses.get(i).length())
                    max = anses.get(i).length();
            }

            return max;
        }

        // 判断两个字符串是否有相同的字符
        // 有相同字符，则返回false
        public boolean ifCat(String s1, String s2){
            char[] arr1 = s1.toCharArray();
            char[] arr2 = s2.toCharArray();

            for (int i = 0; i < arr2.length; i++){
                if (s1.contains(String.valueOf(arr2[i])))
                    return false;
            }

            return true;
        }

        // 判断一个字符串中是否有相同的字符
        // 有相同字符，则返回false
        public boolean ifSame(String str){
            for (int i = 0; i < str.length(); i++){
                String parti = String.valueOf(str.toCharArray()[i]);
                if (str.indexOf(parti) != str.lastIndexOf(parti))
                    return false;
            }
            return true;
        }

        // 采用回溯算法寻找可行的字符串
        public void search(List<String> arr, String weget, int i, List<String> anses){
            if (i >= arr.size()){
                anses.add(weget);
                return;
            }

            for (int j = i; j < arr.size(); j++){
                if (ifCat(weget, arr.get(j)) && ifSame(arr.get(j))){
                    String newget = weget + arr.get(j);
                    search(arr, newget, j+1, anses);
                }else{
                    continue;
                }
            }

            search(arr, weget, i+1, anses);
        }
    }

